# Задание 1

## Цель
Подсчет числа единиц в двоичном представлении числа без массивов и операций деления

## Задачи
1. Написать программу, которая подсчитывает количество единиц в двоичной записи введенного числа
2. Не использовать массивы и операции деления

## Описание рассматриваемого алгоритма
1. На вход функции подается число n
2. Создается счетчик количества единиц w = 0
3. Запускается цикл while n > 0, в котором:
   - С помощью побитовой операции умножения на маску 1<sub>2</sub> определяется младший бит числа, который прибавляется к счетчику
   - Происходит побитовый сдвиг исходного числа на 1 бит вправо
4. Функция возвращает полученное значение w

## Описание результатов проводимых исследований
Результатом данной функции является количество единиц в двоичном представлении введенного числа

## Листинг программы
```c++
unsigned int count_ones (unsigned long long n) {
  unsigned int w = 0;
  while (n > 0) {
    w += n & 1;
    n = n >> 1;
  }
  return w;
}
```

# Задание 2

## Цель
Подсчет числа единиц в двоичном представлении числа с помощью вспомогательного массива

## Задачи
1. Написать программу, которая подсчитывает количество единиц в двоичной записи введенного числа
2. Использовать вспомогательный массив

## Описание рассматриваемого алгоритма
1. На вход функции подается число n
2. Задается массив arr содержащий заранее рассчитанное количество единиц для чисел из промежутка [0; 15]
3. Создается счетчик количества единиц w = 0
4. Запускается цикл while n > 0, в котором:
   - С помощью побитовой операции умножения на маску 15 (1111<sub>2</sub>) определяется четыре младшиx бита числа, которые рассматриваются как индекс массива
   - К счетчику прибавляется значение массива по этому индексу
   - Происходит побитовый сдвиг исходного числа на 4 бита вправо
5. Функция возвращает полученное значение w

## Описание результатов проводимых исследований
Результатом данной функции является количество единиц в двоичном представлении введенного числа

## Листинг программы
```c++
unsigned char arr[16] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};

unsigned int count_ones (unsigned long long n) {
  unsigned int w = 0;
  while (n > 0) {
    w += arr[n & 15];
    n = n >> 4;
  }
  return w;
}
```

# Задание 3

## Цель
Статистика по количеству единиц в двоичном представлении чисел от 0 до 2<sup>k</sup> - 1, с помощью перебора и функции из 1 или 2 пункта

## Задачи
1. Написать программу, которая методом перебора подсчитывает статистику по количеству единиц в двоичном представлении чисел от 0 до 2<sup>k</sup> - 1
2. Использовать функцию из задания 1 или 2

## Описание рассматриваемого алгоритма
1. На вход программы подается число k
2. Создается массив stats, размера k + 1, изначально заполненный нулями, и объявляется переменная power = 1
3. В цикле от 0 до k - 1:
   - Переменная power умножается на 2
4. В цикле i от 0 до power - 1:
   - Инкремент элемента массива с индексом count_ones(i)
5. Полученный массив выводится на экран

## Описание результатов проводимых исследований
Результатом данной программы является вывод статистики по количеству чисел от 0 до 2<sup>k</sup> - 1 для каждого возможного количества единиц от 0 до k

## Листинг программы
```c++
#include "stdio.h"

unsigned char arr[16] = {0, 1, 1, 2, 1, 2, 2, 3,
                         1, 2, 2, 3, 2, 3, 3, 4};

unsigned char count_ones (unsigned long long n) {
  unsigned char w = 0;
  while (n > 0) {
    w += arr[n & 15];
    n = n >> 4;
  }
  return w;
}

int main() {
  int k;
  scanf("%d", &k);
  int stats[k + 1] = {0};

  unsigned long long power = 1;
  for (int i = 0; i < k; i++)
    power *= 2;

  for (unsigned long long i = 0; i < power; i++)
    stats[count_ones(i)]++;

  for (int i = 0; i <= k; i++)
    printf("with %d ones: %d\n", i, stats[i]);
}
```

# Задание 4

## Цель
Статистика по количеству единиц в двоичном представлении чисел от 0 до 2<sup>k</sup> - 1, с помощью численного расчета

## Задачи
1. Написать программу, которая подсчитывает статистику по количеству единиц в двоичном представлении чисел от 0 до 2<sup>k</sup> - 1 с помощью численного расчета
2. Использовать функцию вычисления биноминального коэффициента или треугольник Паскаля

## Описание рассматриваемого алгоритма
1. На вход программы подается число k
2. Создается два массива: prev и now, длины k + 1, заполненных нулями
3. Нулевой элемент массива now задается равным 1
4. В цикле i от 0 до k:
   1. Копирование всех элементов из now в prev
   2. В цикле x от 1 до k:
      - Элемент массива now с индексом x становится равен сумме элементов массива prev с индексами x и x - 1
5. Массив now выводится на экран

## Описание результатов проводимых исследований
Результатом данной программы является вывод статистики по количеству чисел от 0 до 2<sup>k</sup> - 1 для каждого возможного количества единиц от 0 до k, вычисленной с помощью треугольника Паскаля

## Листинг программы
```c++
#include "stdio.h"

int main() {
  int k;
  scanf("%d", &k);

  unsigned long long prev[k + 1] = {0};
  unsigned long long now[k + 1] = {0};
  now[0] = 1;

  for (int i = 1; i <= k; i++) {
    for (int x = 0; x <= k; x++)
      prev[x] = now[x];
    for (int x = 1; x <= k; x++)
      now[x] = prev[x - 1] + prev[x];
  }

  for (int i = 0; i <= k; i++)
    printf("%llu\n", now[i]);
}
```